package com.topInterview;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 思路：组织一个大根堆和一个小根堆
 * 第一个数先进大根堆
 * 如果num<=大根堆头部，则入大根堆，否则进入小根堆
 * 如果两个堆的差值大于等于2，则大的一个堆吐出一个元素给另一个堆
 *
 * @Author: huangzhigao
 * @Date: 2022/2/23 22:16
 */
public class leecode295 {


    class MedianFinder {

        class MyMaxHeapComparator implements Comparator<Integer> {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        }

        class MyMinHeapComparator implements Comparator<Integer> {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        }

        private PriorityQueue<Integer> minQueue;
        private PriorityQueue<Integer> maxQueue;

        public MedianFinder() {
            minQueue = new PriorityQueue<>(new MyMinHeapComparator());
            maxQueue = new PriorityQueue<>(new MyMaxHeapComparator());
        }


        public void addNum(int num) {
            if (maxQueue.isEmpty()) {
                maxQueue.add(num);
            } else {
                if (num <= maxQueue.peek()) {
                    maxQueue.add(num);
                } else {
                    minQueue.add(num);
                }
            }
            balance();
        }

        public double findMedian() {
            if (maxQueue.size() == minQueue.size()) {
                return (double) (maxQueue.peek() + minQueue.peek()) / 2;
            } else {
                return maxQueue.size() > minQueue.size() ? maxQueue.peek() : minQueue.peek();
            }
        }


        public void balance() {
            if (maxQueue.size() == minQueue.size() + 2) {
                minQueue.add(maxQueue.poll());
            }
            if (maxQueue.size() == minQueue.size() - 2) {
                maxQueue.add(minQueue.poll());
            }
        }
    }
}
